package com.dong.ch04_linkedList;

import jdk.nashorn.internal.ir.CallNode;

import java.util.HashMap;
import java.util.Set;
import java.util.TreeMap;

/**
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution19 {
    public static void main(String[] args) {
        Solution19 s = new Solution19();
        int[] arr = {1,2};
        ListNode head = s.build(arr);
        ListNode cur = s.removeNthFromEnd(head,2);
        while(cur!=null) {
            System.out.println(cur.val+"-->");
            cur=cur.next;
        }
    }

    public ListNode build(int[] array) {
        ListNode head = new ListNode(array[0]);
        ListNode cur = head;
        for (int i = 1; i < array.length; i++) {
            cur.next=new ListNode(array[i]);
            cur=cur.next;
        }
        return head;
    }

    //  Definition for singly-linked list.
      public class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
          if(head==null) {
              return null;
          }
          int totalSize = 1;
        HashMap<ListNode,ListNode> preMap = new HashMap<>();
        ListNode next = head.next;
        ListNode pre = head;
        while(next!=null) {
            totalSize++;
            preMap.put(next,pre);
            pre=pre.next;
            next=next.next;
        }
        preMap.put(head,null);
        int positiveIndex = totalSize-n;
        System.out.println("positiveIndex:"+positiveIndex);
        if(positiveIndex<0) return head;
        ListNode node = head;
        int count = 0;
        while(node!=null) {
            if(count==positiveIndex) {
                ListNode preNode = preMap.get(node);
       //         System.out.println("node: "+node.val+",count:"+count+",pre:"+preNode.val);
                if(preNode==null) {
                    ListNode currentHead = head;
                    head=head.next;
                    currentHead.next=null;
                }else {
                    preNode.next=node.next;
                    node.next=null;
                }
            }
            count++;
            node=node.next;
        }
        return head;
    }
}
